package com.sheng.leetcode.year2022.month05.day16;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/05/16
 *
 * 面试题 04.06. 后继者
 *
 * 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
 * 如果指定节点没有对应的“下一个”节点，则返回null。
 *
 * 示例 1:
 *
 * 输入: root = [2,1,3], p = 1
 *
 *   2
 *  / \
 * 1   3
 *
 * 输出: 2
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,null,1], p = 6
 *
 *       5
 *      / \
 *     3   6
 *    / \
 *   2   4
 *  /
 * 1
 *
 * 输出: null
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/successor-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCodeInorderSuccessor {

    //       5
    //     /   \
    //    3     6
    //   / \   / \
    //  2   4 1   0
    //先序遍历/前序遍历：根左右，即先遍历根结点，再遍历左子树，最后遍历右子树（5-3-2-4-6-1-0）
    //中序遍历：左根右，即优先遍历左结点，再遍历根结点，最后遍历右结点（2-3-4-5-1-6-0）
    //后序遍历：左右根，即优先遍历左结点，再遍历右结点，最后遍历根结点（2-4-3-1-0-6-5）
    //层序遍历：从上至下，逐层遍历（5-3-6-2-4-1-0）

    @Test
    public void test01(){
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        TreeNode p = new TreeNode(1);
        TreeNode treeNode = new Solution().inorderSuccessor(root, p);
        System.out.println(treeNode);
    }

}

//Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        //该题要求获取二叉搜索树中序遍历的后一个结点
        List<TreeNode> list = new ArrayList<>();
        ergodic(root, list);
        for (TreeNode treeNode : list) {
            if (treeNode.val == p.val) {

            }
        }
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).val == p.val && i != list.size() - 1) {
                return list.get(i + 1);
            }
        }
        return null;
    }

    public void ergodic(TreeNode root, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        ergodic(root.left, list);
        list.add(root);
        ergodic(root.right, list);
    }
}

//为了找到二叉搜索树中的节点 pp 的后继节点，最直观的方法是中序遍历。
//由于只需要找到节点 pp 的后继节点，因此不需要维护完整的中序遍历序列，
//只需要在中序遍历的过程中维护上一个访问的节点和当前访问的节点。
//如果上一个访问的节点是节点 pp，则当前访问的节点即为节点 pp 的后继节点。
//如果节点 pp 是最后被访问的节点，则不存在节点 pp 的后继节点，返回 \text{null}null。
//
//class Solution {
//    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
//        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
//        TreeNode prev = null, curr = root;
//        while (!stack.isEmpty() || curr != null) {
//            while (curr != null) {
//                stack.push(curr);
//                curr = curr.left;
//            }
//            curr = stack.pop();
//            if (prev == p) {
//                return curr;
//            }
//            prev = curr;
//            curr = curr.right;
//        }
//        return null;
//    }
//}
//
//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/successor-lcci/solution/hou-ji-zhe-by-leetcode-solution-6hgc/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//方法二：利用二叉搜索树的性质
//二叉搜索树的一个性质是中序遍历序列单调递增，因此二叉搜索树中的节点 p 的后继节点满足以下条件：
//后继节点的节点值大于 p 的节点值；
//后继节点是节点值大于 p 的节点值的所有节点中节点值最小的一个节点。
//利用二叉搜索树的性质，可以在不做中序遍历的情况下找到节点 p 的后继节点。
//如果节点 p 的右子树不为空，则节点 p 的后继节点在其右子树中，在其右子树中定位到最左边的节点，即为节点 p 的后继节点。
//如果节点 p 的右子树为空，则需要从根节点开始遍历寻找节点 p 的祖先节点。
//将答案初始化为 null。用 node 表示遍历到的节点，
//初始时 node=root。
//每次比较 node 的节点值和 p 的节点值，执行相应操作：
//如果 node 的节点值大于 p 的节点值，
//则 p 的后继节点可能是 node 或者在 node 的左子树中，
//因此用 node 更新答案，并将 node 移动到其左子节点继续遍历；
//如果 node 的节点值小于或等于 p 的节点值，
//则 p 的后继节点可能在 node 的右子树中，因此将 node 移动到其右子节点继续遍历。
//由于在遍历过程中，当且仅当 node 的节点值大于 p 的节点值的情况下，
//才会用 node 更新答案，因此当节点 p 有后继节点时一定可以找到后继节点，
//当节点 p 没有后继节点时答案一定为 null。
//
//Python3JavaC#C++CJavaScriptGolang
//
//class Solution {
//    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
//        TreeNode successor = null;
//        if (p.right != null) {
//            successor = p.right;
//            while (successor.left != null) {
//                successor = successor.left;
//            }
//            return successor;
//        }
//        TreeNode node = root;
//        while (node != null) {
//            if (node.val > p.val) {
//                successor = node;
//                node = node.left;
//            } else {
//                node = node.right;
//            }
//        }
//        return successor;
//    }
//}
//
//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/successor-lcci/solution/hou-ji-zhe-by-leetcode-solution-6hgc/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//BST 特性 + 递归
//利用 BST 的特性，我们可以根据当前节点 root 与 p 的值大小关系来确定搜索方向：
//
//若有 root.val <= p.val : 根据 BST 特性可知当前节点 root 及其左子树子节点均满足「值小于等于 p.val」，
//因此不可能是 p 点的后继，我们直接到 root 的右子树搜索 p 的后继（递归处理）；
//若有 root.val > p.val : 当第一次搜索到满足此条件的节点时，
//在以 root 为根节点的子树中「位于最左下方」的值为 p 的后继，
//但也有可能 root 没有左子树，因此 p 的后继要么在 root 的左子树中（若有），
//要么是 root 本身，此时我们可以直接到 root 的左子树搜索，
//若搜索结果为空返回 root，否则返回搜索结果。
//代码：
//
//Java
//
//class Solution {
//    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
//        if (root == null) return null;
//        if (root.val <= p.val) return inorderSuccessor(root.right, p);
//        TreeNode ans = inorderSuccessor(root.left, p);
//        return ans == null ? root : ans;
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/successor-lcci/solution/by-ac_oier-xib5/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
